#ifndef __DOUBLELINKLIST_HPP_
#define __DOUBLELINKLIST_HPP_

#include <iostream>
#include <cstddef>
template<typename T>
class DOubleLinkList
{
public:
    DOubleLinkList();
    ~DOubleLinkList();
    void InsertTail(const T& element);
    void RemoveByIndex(size_t index);
    T& FindByIndex(size_t index);
    size_t Size(){return size;}
    template <typename U>
    friend std::ostream &operator<<(std::ostream &os, const DOubleLinkList<U> &list);
private:
    struct Node
    {
        Node(const T& element)
        {
            data = element;
            next = prev = nullptr;
        }
        T data;
        Node *prev;
        Node* next;
    };
    Node* head;
    Node* tail;
    int size;
};

template <typename T>
inline DOubleLinkList<T>::DOubleLinkList():size(0)
{
    tail = head = new Node(T());
}

template <typename T>
inline DOubleLinkList<T>::~DOubleLinkList()
{
    while(head)
    {
        Node* freenode = head;
        head = head->next;
        delete freenode;
    }

}

template <typename T>
inline void DOubleLinkList<T>::InsertTail(const T& element)
{
    Node *node = new Node(element);
    tail->next = node;
    node->prev = tail;
    tail = node;
    size++;
}

template <typename T>
void DOubleLinkList<T>::RemoveByIndex(size_t index)
{
    if(index >= size)
        return;
    Node *node = head;
    for(int i = 0;i < index;i++)
        node = node->next;
    Node *p = node->next;
    node->next = p->next;
     if(p->next != nullptr)
        p->next->prev = node;
    else if(p->next == nullptr)
        tail = node;
    delete p;
    size--;
}

template <typename T>
inline T &DOubleLinkList<T>::FindByIndex(size_t index)
{
    Node *node = head->next;
    for(size_t i = 0; i < index;i++)
        node = node->next;
    return node->data;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const DOubleLinkList<T> &list)
{
    //告诉编译器后面跟着数据类型
    typename DOubleLinkList<T>::Node *node = list.head->next;
    while(node)
    {
        std::cout<<node->data<<" ";
        node = node->next;
    }
    return os;
}

#endif


